package com.leetcode.algorithm.y19.m01;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

import com.leetcode.algorithm.common.TreeNode;

/**
 * leetcode-cn.com
 * (done)653. 两数之和 IV - 输入 BST
 * (done)671. 二叉树中第二小的节点
 * (done)700. 二叉搜索树中的搜索
 * (done)872. 叶子相似的树
 * @author: jie.deng
 * @time: 2019年1月25日 上午8:51:35
 */
public class MySolution0125 {

	/**
	 * 653. 两数之和 IV - 输入 BST
	 * 
     * 给定一个二叉搜索树和一个目标结果，如果 BST 中存在两个元素且它们的和等于给定的目标结果，则返回 true。
     * 
     * 案例 1:
     * 
     * 输入: 
     *     5
     *    / \
     *   3   6
     *  / \   \
     * 2   4   7
     * 
     * Target = 9
     * 
     * 输出: True
     *  
     * 
     * 案例 2:
     * 
     * 输入: 
     *     5
     *    / \
     *   3   6
     *  / \   \
     * 2   4   7
     * 
     * Target = 28
     * 
     * 输出: False
	 * @param root
	 * @param k
	 * @return
	 */
	public boolean findTarget(TreeNode root, int k) {
		if (root == null) {
			return false;
		}
		List<Integer> list = inorderTraversal(root);
		int size = list.size();
		if (size == 0 || size == 1) {
			return false;
		}
		for (int i = 0; i < size - 1; i++) {
			if (list.get(i) + list.get(i + 1) <= k && list.get(i) + list.get(size - 1) >= k) {
				for (int j = size - 1; j > i; j--) {
					if (list.get(i) + list.get(j) == k) {
						return true;
					}
				}
			}
		}
		return false;
	}
	private List<Integer> inorderTraversal(TreeNode root) {
		List<Integer> list = new ArrayList<Integer>();
		if (root == null) {
			return list;
		}
		Stack<TreeNode> stack = new Stack<TreeNode>();
		TreeNode cur = root;
		while (cur != null || !stack.isEmpty()) {
			while (cur != null) {
				stack.push(cur);
				cur = cur.left;
			}
			if (!stack.isEmpty()) {
				cur = stack.pop();
				list.add(cur.val);
				cur = cur.right;
			}
		}
		return list;
	}
	
    
    /**
     * 671. 二叉树中第二小的节点
     * 
     * 给定一个非空特殊的二叉树，每个节点都是正数，并且每个节点的子节点数量只能为 2 或 0。如果一个节点有两个子节点的话，那么这个节点的值不大于它的子节点的值。 
     * 
     * 给出这样的一个二叉树，你需要输出所有节点中的第二小的值。如果第二小的值不存在的话，输出 -1 。
     * 
     * 示例 1:
     * 
     * 输入: 
     *     2
     *    / \
     *   2   5
     *      / \
     *     5   7
     * 
     * 输出: 5
     * 说明: 最小的值是 2 ，第二小的值是 5 。
     * 示例 2:
     * 
     * 输入: 
     *     2
     *    / \
     *   2   2
     * 
     * 输出: -1
     * 说明: 最小的值是 2, 但是不存在第二小的值。
     * @param root
     * @return
     */
	public int findSecondMinimumValue(TreeNode root) {
		int min = root.val;
		int left = findSecondMinimumValue(root.left, min);
		int right = findSecondMinimumValue(root.right, min);
		if (left == -1 || right == -1) {
			return left * right * -1;
		}
		return Math.min(left, right);
	}

	private int findSecondMinimumValue(TreeNode node, int min) {
		if (node == null) {
			return -1;
		}
		if (node.val != min) {
			return node.val;
		}
		int left = findSecondMinimumValue(node.left, min);
		int right = findSecondMinimumValue(node.right, min);
		if (left == -1 || right == -1) {
			return left * right * -1;
		}
		return Math.min(left, right);
	}
	
	/**
     * 700. 二叉搜索树中的搜索
     * 
     * 给定二叉搜索树（BST）的根节点和一个值。 你需要在BST中找到节点值等于给定值的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 NULL。
     * 
     * 例如，
     * 
     * 给定二叉搜索树:
     * 
     *         4
     *        / \
     *       2   7
     *      / \
     *     1   3
     * 
     * 和值: 2
     * 你应该返回如下子树:
     * 
     *       2     
     *      / \   
     *     1   3
     * 在上述示例中，如果要找的值是 5，但因为没有节点值为 5，我们应该返回 NULL。
     * @param root
     * @param val
     * @return
     */
    public TreeNode searchBST(TreeNode root, int val) {
		if (root == null) {
			return null;
		}
		if (root.val < val) {
			return searchBST(root.right, val);
		} else if (root.val > val) {
			return searchBST(root.left, val);
		}
		return root;
    }
    
    /**
     * 872. 叶子相似的树
     * 
     * 请考虑一颗二叉树上所有的叶子，这些叶子的值按从左到右的顺序排列形成一个 叶值序列 。
     * 
     * 
     * 
     * 举个例子，如上图所示，给定一颗叶值序列为 (6, 7, 4, 9, 8) 的树。
     * 
     * 如果有两颗二叉树的叶值序列是相同，那么我们就认为它们是 叶相似 的。
     * 
     * 如果给定的两个头结点分别为 root1 和 root2 的树是叶相似的，则返回 true；否则返回 false 。
     * 
     *  
     * 
     * 提示：
     * 
     * 给定的两颗树可能会有 1 到 100 个结点。
     * @param root1
     * @param root2
     * @return
     */
	public boolean leafSimilar(TreeNode root1, TreeNode root2) {
		List<Integer> list1 = preorderTraversalRetLeaf(root1);
		List<Integer> list2 = preorderTraversalRetLeaf(root2);
		if (list1.size() != list2.size()) {
			return false;
		}
		for (int i = 0; i < list1.size(); i++) {
			if (list1.get(i) != list2.get(i)) {
				return false;
			}
		}
		return true;
	}
    
	private List<Integer> preorderTraversalRetLeaf(TreeNode root) {
		List<Integer> list = new ArrayList<Integer>();
		if (root == null) {
			return list;
		}
		Stack<TreeNode> stack = new Stack<TreeNode>();
		TreeNode cur = root;
		while (cur != null || !stack.isEmpty()) {
			while (cur != null) {
				if (cur.left == null && cur.right == null) {
					list.add(cur.val);
				}
				stack.push(cur);
				cur = cur.left;
			}
			if (!stack.isEmpty()) {
				cur = stack.pop();
				cur = cur.right;
			}
		}
		return list;
	}
}
